1. Field
The disclosed embodiments generally relate to packet-processing systems for communications networks. More specifically, the disclosed embodiments relate to a method and an apparatus for scheduling both control message packets and traffic packets in a packet-processing pipeline.
2. Related Art
Network processors often include a programmable pipeline to facilitate processing a stream of packets at high data rates, for example up to 100 gigabits per second. A programmable pipeline is often associated with one or more “processing engines” that perform various packet-processing operations, such as accessing a lookup table. Moreover, a programmable pipeline typically interacts with an engine through one or more engine access points (EAPs) located at various stages of the pipeline. For example, an EAP can be used to send a request on behalf of a packet to a packet-processing engine, and to receive a corresponding response which can be integrated into the packet.
An engine is typically accessed by normal “traffic packets” to perform table lookups. In contrast, the engine is less frequently accessed by control-message (CM) packets to perform more time-consuming table-management operations. In order to maximize pipeline throughput, it is desirable to allow traffic packets to use as much of the engine's capacity as possible. Also, because CM packets are comparatively rare, it is undesirable to reserve engine capacity just to service these packets. In normal situations, traffic packets only achieve a 100% load for short periods of time. In other words, there are commonly gaps (unused capacity) in a stream of traffic packets. Hence, it is desirable for the engine to use these gaps to process requests for CM packets. However, using these gaps for CM packets involves performing queuing operations, and because queues are bounded in size it is important to ensure that no traffic packets or CM packets will be dropped because of queue overflow conditions.
However, it is complicated to ensure against queue overflow conditions because the mix between traffic packets and CM packets is typically controlled by an arbiter at the entrance to the programmable pipeline. Once a packet enters the pipeline, the packet proceeds through all of the pipeline stages without stalling. The engine has no other connection to the arbiter. (Note that because of the high pipeline speeds and the relatively large propagation delay between the engine and the arbiter, it is impractical to send feedback signals from the engine to the arbiter.)
A technique disclosed in U.S. patent application Ser. No. 11/722,470 (entitled “Method for Reducing Buffer Capacity in a Pipeline Processor,” by the same inventors as the instant application, filed 28 Nov. 2007) ensures against queue overflow by letting one or more CM packets borrow engine capacity from the traffic packets, wherein the gaps in the traffic packets are used to regain the borrowed costs. Note that this borrowed engine capacity manifests itself as queue buildup, and this buildup needs to return to a low level, before new CM packets can be sent.
The above-described technique assumes that the location in the pipeline where you regain capacity (from gaps) is also the same location where you use the capacity (to service requests for traffic packets and CM packets). However, in many situations it is desirable for CM packets to use different engine access points (EAPs) from traffic packets. In this case, engine capacity is regained at different pipeline locations than where the capacity is used and the above-described technique may not operate properly.
Hence, what is needed is a method and an apparatus for scheduling packets to enter a programmable pipeline which operates in situations where CM packets and traffic packets access an engine from different pipeline locations.